package com.clps.algorithm.chapter13.恢复IP;

import java.util.LinkedList;
import java.util.List;

/**
 * 输入一个只包含字符串,列出所有可能恢复出来的ip,列如:字符串:"10203040.可能恢复出3个ip分别为"10.20.30.40"，"102.0.30.40"和"10.203.0.40"。
 */
public class demo01 {

    public static void main(String[] args) {

    }

    public List<String> restoreipAddress(String s){
        List<String> result = new LinkedList<>();
        helper(s, 0, 0, "", "", result);
        return  result;
    }

    private void helper(String s, int index, int segIndex, String seg, String ip, List<String> result) {

        if(index == s.length() && segIndex ==3 && isValidseg(seg)){
            result.add(ip+seg);
        } else if (index <s.length() && segIndex <=3) {
            char ch = s.charAt(index);

            if(isValidseg(seg+ch)){
                helper(s,index+1,segIndex,seg+ch,ip,result);
            }

            if(seg.length()>0 && segIndex<3){
                helper(s,index,segIndex+1,"",ip+seg+".",result);
            }
        }
    }

    private boolean isValidseg(String seg) {
        return  Integer.valueOf(seg) <=255 && (seg.equals("0") || seg.charAt(0)!='0');
    }
}


